#include <stdio.h>
#include <stdlib.h>

typedef struct list {
  int item;
  struct list *next;
} list;

list *search_list(list *l, int x) {
  if (l == NULL) {
    return NULL;
  }

  if (l->item == x) {
    return l;
  } else {
    return search_list(l->next, x);
  }
}

// @ME
list *search_list_iterative(list *l, int x) {
  if (l == NULL) {
    return NULL;
  }

  list *c = l;

  do {
    if (c->item == x) {
      return c;
    }
    c = c->next;
  } while (c->next != NULL);

  return NULL;
}

// essentially, l points to the list head, which is an list*
// it could point to the another item in the list but that would break the list
void insert_list(list **l, int x) {
  list *p;
  p = malloc(sizeof(list));
  p->item = x;
  p->next = *l;
  *l = p;
}

// This returns the item right behind x
list *item_ahead(list *l, list *x) {
  if ((l == NULL) || (l->next == NULL)) {
    return NULL;
  }

  if ((l->next) == x) {
    return l;
  } else {
    return item_ahead(l->next, x);
  }
}

// @ME
list *item_ahead_iterative(list *l, list *x) {
  if ((l == NULL) || (l->next == NULL)) {
    return NULL;
  }

  list *c = l;

  do {
    if (c->next == x) {
      return c;
    } else {
      c = c->next;
    }
  } while (c->next != NULL);

  return NULL;
}

void delete_list(list **l, list **x) {
  list *p;
  list *prev;

  p = *l;
  prev = item_ahead(*l, *x);

  // if l -> NULL or x -> NULL or the element to delete just isn't found
  if (prev == NULL) {
    prev = *l;
    // The original code just had this, which didn't let me do
    // delete_list(&l, &l)
    // Yes I know that's terrible but yeah
    *l = p->next;
    free(prev);
    return;
  } else {
    prev->next = (*x)->next;
  }

  free(*x);
}

// Recursion is great
void print_list(list *l) {
  if (l == NULL)
    return;

  if (l->next == NULL)
    printf("%d\n", l->item);
  else {
    printf("%d -> ", l->item);
    print_list(l->next);
  }
}

int main(void) {
  list *l = malloc(sizeof(list));
  l->item = 1;
  l->next = NULL;

  insert_list(&l, 2);
  insert_list(&l, 3);
  insert_list(&l, 4);
  insert_list(&l, 5);
  insert_list(&l, 6);

  print_list(l);

  list *t1 = search_list_iterative(l, 5);
  list *t2 = search_list_iterative(l, 8);

  list *to_delete = search_list_iterative(l, 6);

  delete_list(&l, &to_delete);
  print_list(l);

  list *t = l;

  delete_list(&l, &t);
  print_list(l);

  printf("t1 = %d, t2 = %d\n", t1 ? t1->item : 0, t2 ? t2->item : -1);
}
